package ch5.msd;

import java.util.Arrays;

/**
 * @author : DuJiabao
 * @Date : 2021/2/7 22:43
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc : 高位优先的字符串排序
 * 通过递归的方式实现。逐个字符比较。前面的字符排好序之后，就根据前面的字符，进行分组递归排序。
 * 排序通过之前学的键索引计数法。针对不同的ASCII码进行计数。值得一提的是，为了实现不同长度字符串的排序，将缺少字符的位置赋值为-1。
 *
 */
public class MSD {
  private static int R = 256; // 基数，也就是ASCII码的个数
  private static String[] aux; // 暂时存放的地方

  public static void main(String[] args) {
    String[] str = new String[]{
            "fadfarqr", "rqesv", "fatet", "hgjey", "bnghd", "qr43435", "hgjye", "adth", "hgggt", "rweryr", "4454te", "twet", "g454wt"
    };
    aux = new String[str.length];
    sort(str, 0, str.length - 1, 0);
    System.out.println(Arrays.toString(str));
  }

  /**
   * 取出字符，转换成ASCII码形式。如果超出长度了，就返回-1
   *
   * @param s
   * @param d
   * @return
   */
  private static int charAt(String s, int d) {
    if (d < s.length()) return s.charAt(d);
    else return -1;
  }

  /**
   * 针对字符串数组的子数组进行排序
   *
   * @param a     字符串
   * @param start 左闭
   * @param end   右闭
   * @param d     排序位置
   */
  private static void sort(String[] a, int start, int end, int d) {
    if (end - start <= 1) return;  // 终止条件
    // 先计数
    int[] count = new int[R + 2];
    for (int i = start; i <= end; i++) {
      count[charAt(a[i], d) + 2]++; // 计数。因为空字符占了-1位置，因此，需要+2，以保证后续的功能能正常进行
    }

    // 计算每个组的开始坐标
    for (int i = 0; i < count.length - 1; i++) {
      count[i + 1] += count[i];
    }

    // 迁移位置
    for (int i = start; i <= end; i++) {
      aux[count[charAt(a[i], d) + 1]++] = a[i];  // ASCII + 1 才是真正的位置。然后索引递增。aux是从0开始保存的，这是个坑啊！
    }

    // 回写 aux是从0开始保存的，因此要从0开始迁移回去
    for (int i = start; i <= end; i++) {
      a[i] = aux[i - start];
    }

    // 递归每个字符排序
    for (int i = 0; i < R; i++) {
      sort(a, start + count[i], start + count[i + 1] - 1, d + 1);
    }
  }
}
